# Q: Given a singly linked list, devise a time- and space-efficient algorithm
# to find the mth-to-last element of the list. Implement your algorithm, taking
# care to handle relevant error conditions. Define mth to last such that when m
# = 0, the last element of the list is returned.
#
# A: Naive solution would be to iterate through each element, and for each
# element iterate through the elements after it m time and see if it hits the
# end. This will O(n^2) time.
#
# Another better solution would be to keep track of a pointer, initialized with
# the head of the list. Then walk through the list one by one and keep the count
# of how many elements we've seen so far. Start advancing this pointer to the
# next element only when the count is greater m. When the iteration hits the end
# of the list, return this pointer or None if the count is less than m. This
# will take only O(n).

from Commons import *

def naive_mth_element_to_last_element_of_list(thelist, m):
   node = thelist
   while node:
      thenode, i = node, 1
      while thenode and i < m:
         i += 1
         thenode = thenode.nextNode
      if thenode and not thenode.nextNode and i == m:
         return node
      node = node.nextNode
   return None

def better_mth_element_to_last_element_of_list(thelist, m):
   node = ans = thelist
   count = 0
   while node:
      if count >= m:
         ans = ans.nextNode
      count += 1
      node = node.nextNode
   return ans if count >= m else None

data = list(range(10))
thelist = list_to_linked_list(data)
print(data)
for n in range(len(data)):
   naive = naive_mth_element_to_last_element_of_list(thelist, n)
   better = better_mth_element_to_last_element_of_list(thelist, n)
   print(naive, better)
   assert naive == better

